package chapter22;

import java.util.List;

/**
 * 基本图算法-深度优先遍历
 * <p>
 * 有路径先遍历路径
 */
public class DFS {
    static int time = 0;

    public static void dfs(List<Node> V, Node[] G) {
        time = 0;
        for (Node u : V) {
            if (G[u.key].color == Node.WHILE) {
                dfsVisit(G, G[u.key]);
            }
        }
    }

    public static void dfsVisit(Node[] G, Node u) {
        time = time + 1;
        u.d = time;
        u.color = Node.GRAY;
        // 遍历u相邻边的v
        Node next = u.next;
        while (next != null) {
            Node v = G[next.key];
            if (v.color == Node.WHILE) {
                v.p = u;
                dfsVisit(G, v);
            }
            next = next.next;
        }
        u.color = Node.BLACK;
        time = time + 1;
        u.f = time;
    }
}
